<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>04_希尔排序</title>
  </head>
  <body>
    <script>
      function shellSort(arr) {
        // 1.获取数组的长度
        const length = arr.length

        // 2.初始化增量(间隔)
        let gap = Math.floor(length / 2)

        // 3.while循环(gap不断减小)
        while (gap >= 1) {
          // 4.以gap作为分隔，进行分组，对分组进行插入排序
          for (let i = gap; i < length; i++) {
            let j = i
            const temp = arr[i]
            // gap - 1 时就不能再左移了
            while (arr[j - gap] > temp && j - gap >= 0) {
              arr[j] = arr[j - gap]
              j = j - gap
            }
            // 5.将j位置的元素赋值temp
            arr[j] = temp
          }
          // 6.改变增量
          gap = Math.floor(gap / 2)
        }

        return arr
      }
      var arr = [1, 23, 434, 121, 4, 34, 5345, 232, 12, 32, 212, 121]
      console.log(shellSort(arr))
    </script>
  </body>
</html>
